Collections类中常用算法之Rotate

Collections类简介

Collections类是java集合框架的一个类，其主要是一些通用的作用于Collection的算法，如排序，求极值，混淆(shuffle)等。
引用Java官方文档的介绍

The polymorphic algorithms described here are pieces of reusable functionality provided by the Java platform. All of them come from the Collections class, and all take the form of static methods whose first argument is the collection on which the operation is to be performed. The great majority of the algorithms provided by the Java platform operate on List instances, but a few of them operate on arbitrary Collection instances.

Collections类的方法都是静态方法，每一种方法都对应一种集合算法的实现，且每一种实现都有两种，一种是适用于实现了RandomAccess接口的集合类（例如ArrayList），另一种是适用于序列存储的，例如（LinkedList）。

Collections类包含的算法实现大致如下：

排序
排序采用归并排序，所以排序算法是稳定的，时间复杂度是确定的。
混淆
常规的集合数据操作（适用于List）
包括reverse、fill、copy、swap、addAll等
搜索（适用于List）
binarySearch
极值
求集合的最大元素、最小元素

Collections中的大多数算法都只是适用于List，接下来讨论的Rotate方法就是只适用于List的。
使用与List的算法主要有：

sort
shuffle
reverse
rotate
swap
replaceAll
fill
copy
binarySearch
indexOfSubList
lastIndexofSubList

Rotate方法使用

Rotate方法需要一个参数distance，该方法将一个List旋转多少长度为distance。假如有个序列列list是[a,b,c,d]，调用方法Collections.rotate(list, 1)后，得到的list就变为了[d,a,b,c]。
调用此方法后，位置i上的元素将变为位置(i - distance) mod list.size()的元素，0 <= i < list.size()。distance可以为正数、0、负数。正数代表向前（下标值变大的方向）旋转，负数代表向后旋转。调用方法Collections.rotate(list, -1)后，得到的list就变为了[b,c,d,a]。

这个方法常常和List的subList方法结合使用，用于将一个list的某个或多个元素进行移动，而不破坏其余元素的顺序。例如为了将某个list的位置j的元素向前移动到k的位置。（设移动的距离为d（d >= 0），k = j + d + 1）。

1	Collections.rotate(list.subList(j, k+1), -1);

举个栗子，例如[a,b,c,d,e]，将b元素向前移动三个位置

1	Collections.rotate(list.subList(1, 5), -1);

调用后得到list为[a,c,d,e,b]。

Rotate方法源码分析

Rotate方法的方法原型为

1	public static void rotate(List<?> list, int distance)

Rotate方法有两种实现，一种适用于实现了RandomAccess接口的List（类似数组的随机访问性质）或者size小于阈值的序列存储的List，另一种是size大于阈值的序列存储（通常是指链表的形式存储的）的List。

关于该方法的源码为

public static void rotate(List<?> list, int distance) {
      if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)
          rotate1(list, distance);
      else
          rotate2(list, distance);
  }

其中rotate1对应于第一种的实现，rotate2对应于第二种的实现。

对于rotate1的实现具体的做法是，将序列的第一个元素交换至正确的位置i，此时原来在位置i的元素就是一个错误放置的元素displaced，然后计算该元素正确放置的位置i，并将其放置到位置i，此时又得到一个错误放置的元素displaced，重复此过程直到错误放置的元素displaced被放置到了第一个位置。（即i == 0）。


private static <T> void rotate1(List<T> list, int distance) {
    int size = list.size();
    if (size == 0)
        return;
    distance = distance % size;
    if (distance < 0)
        distance += size;//将distance化为到范围为0到size - 1的区间
    if (distance == 0)
        return;

    for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {
        T displaced = list.get(cycleStart);
        int i = cycleStart;
        //从cycleStart开始，迭代式的将错误放置的元素放置到正确的位置，直到某个元素被放置到了cycleStart
        //此时，应该结束do...while循环，因为如果继续循环得到的结果就是啥也没干，因为上一轮的循环已经
        //将此次循环访问到的位置的元素放正确了，此时应该换下一个位置作为起点cycleStart，继续执行直到
        //被正确放置的元素的个数nMoved达到了size个
        do {
            i += distance;
          //此处i的范围是 0 ~ 2*size
          //当i大于size且小于2 * size的时候，此时i= i mod size 等价于 i = i - size
            if (i >= size)
                i -= size;
            //此时i的范围为0 ~ size - 1
            displaced = list.set(i, displaced);
            nMoved ++;//记录已经被正确放置的元素的个数
        } while (i != cycleStart);//当i回到起点后，退出本次循环
    }
}

对于rotate2的实现与上面的实现完全不一样，因为考虑到rotate2适用于的是类似于采用链表存储的List，因此不具有随机访问的特性。因此该实现采用的是将原list在-distance mod size处使用subList方法拆分为两个子列表s1，s2，并分别反转俩链表revese(s1)，reverse(s2)，最后再将整个链表反转，reverse(list)。

  private static void rotate2(List<?> list, int distance) {
      int size = list.size();
      if (size == 0)
          return;
      int mid =  -distance % size;
      if (mid < 0)
          mid += size;//确保mid位于0 ~ size的区间
      if (mid == 0)
          return;
//分别反转两个子链表
      reverse(list.subList(0, mid));
      reverse(list.subList(mid, size));
      //最后反转整个链表 两次反转确保俩子链表的元素的的相对位置不变
      reverse(list);
  }

示意图

示意图中(1) (2) (3)分别对应三次链表反转。由示意图中大致可以看出，前两次反转子链表的目的是为了将原链表的首末连在一起，并将mid指向的的元素和其逆时针方向的旁边的元素断开。最后整个链表的反转是为了恢复俩子链表的元素的原始相对顺序。

链表的反转通常采用头插法反转。

小结

rotate方法是将链表旋转一定的distance，该方法常常与subList方法结合用户在List中移动某个元素到指定的位置，而不影响其他元素的顺序
rotate有两种实现，一种针对于随机存取的，另一种针对链表式存取的。
两种实现的思想也不一样，一种是通过迭代式的交换，另一种是通过链表的反转实现的。